package practice_2025_8_25;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    /**
     * 三树之和
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int i = nums.length - 1;
        while(i > 1) {
            int target = -nums[i];
            // 转换为两数之和
            int left = 0, right = i - 1;
            while(left < right) {
                if (nums[left] + nums[right] < target) {
                    left++;
                } else if(nums[left] + nums[right] > target) {
                    right--;
                } else {
                    // 添加结果
                    List<Integer> list = new ArrayList<>(
                        Arrays.asList(nums[i], nums[left], nums[right]));
                    res.add(list);
                    // 继续寻找
                    left++;
                    right--;
                    // 去重
                    while(left < right && nums[left] == nums[left-1]) {
                        left++;
                    }
                    while(left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
            }
            // 继续寻找
            i--;
            while(i > 1 && nums[i] == nums[i + 1]) {
                i--;
            }
        }
        return res;
    }

    /**
     * 最长回文子串
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        // dp[i][j]: 以i为起始位置, j为结尾是否为回文子串
        int maxLen = 0;
        int begin = 0;
        for(int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (i == j) {
                    dp[i][j] = true;
                } else if (i + 1 == j && s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = true;
                } else if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1];
                }
                if (dp[i][j] && (j - i + 1) > maxLen) {
                    begin = i;
                    maxLen = j - i + 1;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}